package leetcode.enumerate;

import java.util.HashMap;
import java.util.HashSet;

public class LCR093 {


    public int lenLongestFibSubseq(int[] arr) {

        int[][] dp = new int[arr.length][arr.length];
        HashMap<Integer, Integer> nums = new HashMap();
        nums.put(arr[0], 0);
        nums.put(arr[1], 1);
        int ans = 0;
        for (int i = 2; i < arr.length; i++) { //固定了第三个值
            for (int j = i-1; j > 0 && arr[j] * 2 > arr[i]; j--) { // 枚举第二个值
                if (nums.containsKey(arr[i] - arr[j])) {
                    int k = nums.getOrDefault(arr[i] - arr[j], -1);
                    if (k >= 0) {
                        dp[j][i] = Math.max(3, dp[k][j] + 1); // k,j,i为一组斐波那契数列
                    }
                    ans = Math.max(ans, dp[j][i]);
                }
            }
            nums.put(arr[i], i);
        }
        return ans;
    }



}
